package com.lcy.struct.memory;

import lombok.Data;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

/**
 * @author lucongyang
 * @date Created in  16:57
 * @description
 */
@Data
public class BPlusTreeEngine {

    private int n = 3;

    private BPlusTree root = new BPlusTree();

    public BPlusTreeEngine(int n) {
        this.n = n;
    }

    // 先不考虑数据

    public void addNode(TreeNode treeNode) {
        // 如果祖先节点是叶子节点
        if (this.root.getChildren() == null || this.root.getChildren().size() == 0) {
            int index = treeNode.getIndex().findIndex(this.root.getIndexList());
            this.root.getIndexList().add(index, treeNode.getIndex());
            this.root.addData(index, treeNode.getData());
            // 如果要分裂
            if (this.root.getIndexList().size() >= n) {
                split(this.root);
            }
        }
        // 如果祖先节点不是叶子节点
        else {
            // 先找到在哪个叶子节点上
            BPlusTree leaf = findIdInLeaf(this.root, treeNode);
            int index = treeNode.getIndex().findIndex(leaf.getIndexList());
            leaf.getIndexList().add(index, treeNode.getIndex());
            leaf.addData(index, treeNode.getData());
            // 如果要分裂
            if (leaf.getIndexList().size() >= n) {
                split(leaf);
            }
        }
    }

    private void split(BPlusTree bPlusTree) {
        if (bPlusTree.getIndexList().size() < n) {
            return;
        }
        List<BPlusTree> splitResult = bPlusTree.splitResult();
        Optional.ofNullable(splitResult.get(0).getChildren()).ifPresent(e -> e.forEach(x -> x.setParent(splitResult.get(0))));
        Optional.ofNullable(splitResult.get(2).getChildren()).ifPresent(e -> e.forEach(x -> x.setParent(splitResult.get(2))));
        // 如果是叶子节点，则关联左右节点
        if (bPlusTree.isLeaf()) {
            splitResult.get(0).setLeft(bPlusTree.getLeft());
            if (bPlusTree.getLeft() != null) {
                bPlusTree.getLeft().setRight(splitResult.get(0));
                bPlusTree.getLeft().setRightIndex(splitResult.get(0).getIndexList());
                splitResult.get(0).setLeftIndex(splitResult.get(0).getLeft().getIndexList());
            }
            splitResult.get(0).setRight(splitResult.get(2));
            splitResult.get(0).setRightIndex(splitResult.get(0).getRight().getIndexList());
            splitResult.get(2).setLeft(splitResult.get(0));
            splitResult.get(2).setRight(bPlusTree.getRight());
            if (bPlusTree.getRight() != null) {
                bPlusTree.getRight().setLeft(splitResult.get(2));
                bPlusTree.getRight().setLeftIndex(splitResult.get(2).getIndexList());
                splitResult.get(2).setRightIndex(splitResult.get(2).getRight().getIndexList());
            }
            splitResult.get(2).setLeftIndex(splitResult.get(2).getLeft().getIndexList());
        }
        if (bPlusTree.isRoot()) {
            // 如果是祖先节点
            bPlusTree.setIndexList(splitResult.get(1).getIndexList());
            bPlusTree.setParent(splitResult.get(1).getParent());
            bPlusTree.setChildren(splitResult.get(1).getChildren());
            // 去掉数据节点
            bPlusTree.setDataList(null);
            // 认父
            splitResult.get(0).setParent(bPlusTree);
            splitResult.get(2).setParent(bPlusTree);
            // 纳子
            List<BPlusTree> children = new ArrayList<>();
            children.add(splitResult.get(0));
            children.add(splitResult.get(2));
            bPlusTree.setChildren(children);
            return;
        }
        BPlusTree parent = bPlusTree.getParent();
        // 中间的节点加到父节点上
        int index = splitResult.get(1).getIndexList().get(0).findIndex(parent.getIndexList());
        parent.getIndexList().add(index, splitResult.get(1).getIndexList().get(0));
        // 其他两个新节点是父节点的子节点
        splitResult.get(0).setParent(parent);
        splitResult.get(2).setParent(parent);
        if (parent.getChildren() != null) {
            int oldIndex = parent.getChildren().indexOf(bPlusTree);
            parent.getChildren().remove(oldIndex);
            parent.getChildren().add(oldIndex, splitResult.get(0));
            parent.getChildren().add(oldIndex + 1, splitResult.get(2));
        } else {
            List<BPlusTree> children = new ArrayList<>();
            children.add(splitResult.get(0));
            children.add(splitResult.get(2));
            parent.setChildren(children);
        }
        if (parent.getIndexList().size() >= n) {
            split(parent);
        }
    }

    private BPlusTree findIdInLeaf(BPlusTree current, TreeNode treeNode) {
        // 先找到在哪个子节点上
        int index = treeNode.getIndex().findIndex(current.getIndexList());
        BPlusTree child = current.findChildren(index);
        if (child.isLeaf()) {
            return child;
        } else {
            return findIdInLeaf(child, treeNode);
        }
    }
}
